#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣1. 两数之和
// 【难度】简单
// 【提交】2025.9.15 https://leetcode.cn/problems/two-sum/
// 【标签】哈希表；数组
class Solution_LC0001 {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
 * 模型：哈希表（散列表），用于快速查找元素。
 * 
 * 二、标准解法状态设计
 * 使用哈希表存储已经遍历过的数字及其索引。对于每个数字 nums[i]，检查 target - nums[i] 是否已经在哈希表中。
 * 如果存在，则返回对应的索引；否则将当前数字存入哈希表。
 * 
 * 三、你的实现思路
 * 使用哈希表实现一次遍历即可找到解，效率高且代码简洁。
 * 
 * 四、逐行注释（带细节提醒）
 * unordered_map<int, int> hashtable;  // 键为数值，值为索引
 * for (int i = 0; i < nums.size(); ++i) {  // 遍历数组
 *     auto it = hashtable.find(target - nums[i]);  // 查找互补数
 *     if (it != hashtable.end()) {  // 如果找到互补数
 *         return {it->second, i};   // 返回两个索引
 *     }
 *     hashtable[nums[i]] = i;  // 将当前数值和索引存入哈希表
 * }
 * return {};  // 无解时返回空数组
 * 
 * 五、正确性证明
 * 算法保证每个元素只被处理一次，且在处理当前元素时，检查的是之前已经处理过的元素。
 * 由于两数之和的解必然是一个元素在当前元素之前，一个元素在当前元素之后（或相同），
 * 因此当遍历到第二个元素时，一定能找到第一个元素。
 * 
 * 六、复杂度
 * 时间：O(n)，只需遍历数组一次，哈希表的查找和插入操作平均时间复杂度为 O(1)。
 * 空间：O(n)，最坏情况下需要存储所有元素。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，只需一次遍历；
 *   - 代码简洁，实现高效；
 *   - 使用哈希表快速查找，避免暴力枚举。
 * 缺点：
 *   - 需要额外的空间存储哈希表；
 *   - 对于极端情况（如大量哈希冲突），性能可能下降。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (nums.empty()) return {};
 * 2. 使用 reserve 方法预分配哈希表空间以提高性能：
 *    hashtable.reserve(nums.size());
 * 3. 对于特殊场景（如已排序数组），可以使用双指针法进一步降低空间复杂度。
 * 
 * 九、一句话总结
 * 哈希表是解决两数之和问题的经典方法，你的实现准确且高效，只需稍作优化即可处理更大规模的数据。
 */